/*
 * 1219. 在排序链表中插入一个节点
 * 在链表中插入一个节点。
 * https://www.lintcode.com/problem/insert-node-in-sorted-linked-list/description
 * 
 * 样例
 * 给出一个链表 1->4->6->8 和 val = 5.。
 * 插入后的结果为 1->4->5->6->8。
 * 
 * 2018.06.09 @jeyming
 */
package insert_node_in_sorted_linked_list_1219;

//Definition for ListNode
class ListNode {
	int val;
	ListNode next;
	ListNode(int x) {
		val = x;
		next = null;
	}
}

public class Insert_node_in_sorted_linked_list_1219 {

	/**
	 * @param head: The head of linked list.
	 * @param val: An integer.
	 * @return: The head of new linked list.
	 */
	public static ListNode insertNode(ListNode head, int val) {
		// write your code here
		ListNode p = head;
		if(p != null){
			if(p.val < val){
				while(p != null){
					if(p.val <= val){
						if((p.next != null) && (p.next.val >= val)){
							ListNode q = new ListNode(val);
							q.next = p.next;
							p.next = q;
							break;
						}
						if(p.next == null){
							ListNode q = new ListNode(val);
							p.next = q;
							break;
						}
					}
					p = p.next;
				}
			} else {
				ListNode q = new ListNode(val);
				q.next = p;
				return q;				
			}
		} else {
			head = new ListNode(val);
		}
		return head;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ListNode q = new ListNode(1);
		ListNode p = insertNode(q,0);
		while(p != null) {
			System.out.println(p.val);
			p = p.next;
		}
	}

}
